#!usr/bin/env python  
# -*- coding:utf-8 _*-
""" 
@author:pengfeifu
@file: 二分查找.py 
@version:
@time: 2021/11/13 
@email:1324734112@qq.com
@desc： 
@function：常用函数
二分查找,时间复杂度：O(logN)
使用场景：有序列表查询
思路：两个变量，left，与，right
middle=(left+right)//2 整除得到的下标
如果value<list[middle] right左移到middle-1处
如果value>list[middle],left右移到middle+1处
相等则找到，
如果left>right，找不到元素位置
list=[1,2,3,4,5,6,7,8,9]
"""

# 计算方法的耗时
from cal_time import *


# 二分查找
@cal_time
def binary_search(li, value):
    left, right = 0, len(li) - 1
    while left <= right:
        middle = (left + right) // 2
        if value == li[middle]:
            return middle
        elif value > li[middle]:  # left右移到middle+1处
            left = middle + 1
        else:  # value<list[middle] right左移到middle-1处
            right = middle - 1
    else:  # 不满足while循环的语句块
        return None


# 线性查找（顺序查找）
@cal_time
def search_list(li, value):
    # dict_value = enumerate(li)
    for index, val in enumerate(li):
        if val == value:
            return index


if __name__ == "__main__":
    list_arr = list(range(100000000))
    binary_search(list_arr, 200000)
    search_list(list_arr, 200000)
